@proceedings{List2007,
title = {
General Polynomial Time Decomposition Algorithms
},
author = {Nikolas List and Hans Ulrich Simon},
year = {2007},
page = {303--321},
volume = {v8},
url = {http://jmlr.csail.mit.edu/papers/v8/list07a.html}
,abstract = {
<p>
We present a general decomposition algorithm that is uniformly
applicable to every (suitably normalized) instance of Convex 
Quadratic Optimization and efficiently approaches an optimal 
solution. The number of iterations required to be within <i>&#949;</i>
of optimality grows linearly with 1/<i>&#949;</i> and quadratically 
with the number <i>m</i> of variables. The working set selection can be
performed in polynomial time. If we restrict our considerations
to instances of Convex Quadratic Optimization with at most <i>k<sub>0</sub></i> 
equality constraints for some fixed constant <i>k<sub>0</sub></i> plus some 
so-called box-constraints (conditions that hold for most
variants of SVM-optimization), the working set is found in linear 
time. Our analysis builds on a generalization of the concept 
of rate certifying pairs that was introduced by Hush and Scovel. 
In order to extend their results to arbitrary instances of Convex 
Quadratic Optimization, we introduce the general notion of a rate 
certifying <i>q</i>-set. We improve on the results by Hush and Scovel (2003) 
in several ways. First our result holds for  Convex Quadratic
Optimization whereas the results by Hush and Scovel are specialized to
SVM-optimization. Second, we achieve a higher rate  of convergence
even for the special case of SVM-optimization (despite the generality
of our approach). Third, our analysis is technically
simpler.
</p><p>
We prove furthermore that the strategy for working set selection which 
is based on rate certifying sets coincides with a strategy which is 
based on a so-called "sparse witness of sub-optimality". Viewed from this 
perspective, our main result improves on convergence results 
by List and Simon (2004) and Simon (2004) by providing convergence rates 
(and by holding under more general conditions). 
</p>
}
}